package com.tcm.day06;

import sun.reflect.generics.tree.Tree;

/**
 * 根据前序和中序遍历构建二叉树
 */
public class Code05_BuildTreeFromPreIn {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if(preorder == null || inorder == null || preorder.length != inorder.length) return null;

        return buildTree(preorder, 0, preorder.length-1, inorder,0, inorder.length-1);
    }

    public TreeNode buildTree(int[] preorder, int L1, int R1, int[] inorder, int L2, int R2) {

        if(L1 > R1){
            return null;
        }
        TreeNode head = new TreeNode(preorder[L1]);
        if(L1 == R1){
            return head;
        }

        int idx = 0;
        while(inorder[idx] != preorder[L1]){
            idx++;
        }

        head.left = buildTree(preorder, L1+1, L1+idx-L2, inorder, L2, idx-1);
        head.right = buildTree(preorder, L1+idx-L2+1, R1, inorder, idx+1, R2);
        return head;
    }

}
